package algorithm.t202111;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/11/16 8:19
 * @description :6道
 * 平常的一天，希望可以拿到国家贫困补助（大学四年第一次），还有上学期的生源地贷款补助，唉，花呗欠了2000，难受。也想换个手机，毛病确实有点多了，努力，奋斗。
 * persevere to last
 * 2021.11.16
 * 李红磊
 * 2021年11月16日21:06:30
 */
public class t20211116 {

    //391.完美矩形
    public boolean isRectangleCover(int[][] rectangles) {
        if (rectangles == null) return false;
        int X1 = Integer.MAX_VALUE, Y1 = Integer.MAX_VALUE;//X1,Y1表示完美矩阵的左下顶点
        int X2 = Integer.MIN_VALUE, Y2 = Integer.MIN_VALUE;//X2,Y2表示完美矩阵的右上顶点
        // 小矩形面积之和
        int areas = 0;//若该矩阵可以形成完美矩形，则小矩形面积只和必然等于完美矩阵面积（此为必要条件，不是充分条件

        /*
        因此，我们可以在遍历小矩形的同时记录顶点出现的情况。如果当前顶点没有遍历过，则将其加入到集合中，否则将其从集合中删除
        。如果最后集合中只包含可能的完美矩形的四个顶点，那么说明例子是合法的，否则说明无法构成完美矩形。

         */
        HashSet<String> hashSet = new HashSet<>();//记录所有顶点出现的情况。注意：若可以形成完美矩阵，完美矩阵的四个顶点只会出现一次

        for (int i = 0; i < rectangles.length; i++) {
            //拿出一个小矩阵
            int x1 = rectangles[i][0], y1 = rectangles[i][1], x2 = rectangles[i][2], y2 = rectangles[i][3];
            //更新左下，右上顶点
            X1 = Math.min(x1, X1);
            Y1 = Math.min(Y1, y1);
            X2 = Math.max(X2, x2);
            Y2 = Math.max(Y2, y2);

            //将此小矩阵面积加上
            areas += (x2 - x1) * (y2 - y1);

            String[] tem = {x1 + "" + y1, x2 + "" + y2, x1 + "" + y2, x2 + "" + y1};

            for (String s : tem) {
                if (hashSet.contains(s)) {
                    hashSet.remove(s);
                } else {
                    hashSet.add(s);
                }
            }


        }

        int expected = (X2 - X1) * (Y2 - Y1);//最终完美矩阵的面积
        //判断完美矩阵面积和小矩阵面积之和 是否相等
        if (expected != areas) return false;

        //检查顶点 出现的次数
        if (hashSet.size() > 4 || !hashSet.contains(X1 + "" + Y1) || !hashSet.contains(X2 + "" + Y2) || !hashSet.contains(X1 + "" + Y2) || !hashSet.contains(X2 + "" + Y1))
            return false;

        return true;
    }

    //剑指11.旋转数组的最小数字
    public int minArray(int[] numbers) {
        return -1;
    }

    //剑指50.第一个只出现一次的字符
    public char firstUniqChar(String s) {

        ArrayDeque<Character> deque = new ArrayDeque<>();

        return ' ';
    }

    //剑指32.从上到下打印二叉树1
    public int[] levelOrder(TreeNode root) {
        if (root == null) return new int[0];
        if (root.left == null && root.right == null) return new int[]{root.val};
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        deque.addLast(root);
        ArrayList<Integer> list = new ArrayList<>();

        while (!deque.isEmpty()) {

            TreeNode poll = deque.poll();
            list.add(poll.val);

            if (poll.left != null) deque.addLast(poll.left);
            if (poll.right != null) deque.addLast(poll.right);

        }
        int[] ans = new int[list.size()];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = list.get(i);
        }

        return ans;
    }

    //剑指32.从上到下打印二叉树2
    public List<List<Integer>> levelOrder2(TreeNode root) {
        return null;
    }

    //剑指32.从上到下打印二叉树2
    public List<List<Integer>> levelOrder3(TreeNode root) {
        ArrayDeque<Object> queue = new ArrayDeque<>();
        return null;
    }


    public static void main(String[] args) {
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        deque.addLast(1);
        deque.addLast(2);
        deque.addLast(3);

        System.out.println(deque.poll());
        System.out.println(deque.poll());
    }

}
